#pragma once
#define BLACK 0
#define RED 1
	template<class K, class V>
	struct RBTNode {
		  struct RBTNode* _left;
		  struct RBTNode* _right;
		 struct RBTNode* _parent;
	
			  bool color; //usr0为黑色，1为红色
		   pair<K, V> _kv;

		   RBTNode(pair<K, V>& kv)
			   :_left(nullptr)
			   , _right(nullptr)
			   , _parent(nullptr)
			   , color(RED)
			   , _kv(kv)
		   {

		   }
	};


	 template<class K, class V>
	class RBTree
	{
		typedef  struct RBTNode<K,V>  Node;
			 private:
					  Node* _root;
			public:
						RBTree()
						:_root(nullptr)
							{
					
						  }
				
							  bool insert(pair<K, V>& data)
							  {
								if (_root == nullptr)
									{
									  _root = new Node(data);
									}
					
								Node* parent = nullptr;
								Node* tmp = _root;
								Node* cur = new Node(data);
								while (tmp)
								   {
										 if (tmp->_kv.first>data.first)
										  {
												   parent = tmp;
												   tmp = tmp->_left;
										   }
											 else if (tmp->_kv.first<data.first)
											 {
		                   						  parent = tmp;
												   tmp = tmp->_right;
											  }
											 else
											  {
													return false;
											  }
								   }
						
								if (parent->_kv.first > data.first)
									parent->_left = cur;
								else
									parent->_right = cur;
						
										//插入成功,需要看有没有违反红黑树的5条性质	
								if (gradparent->_left = parent)
									Node* uncle = gradparent->_right;
								else
									Node* uncle = gradparent->_left;
								//为什么插入节点的时候我们默认为红色呢？因为如果插入黑色，绝对破坏了性质：从一个节点出发，路径上的黑色
								//节点的数量是相同的
								while (cur&&parent->color==1)//cur和parent同时为红时出现问题
								{
									Node* gradparent = parent->_parent;
									//unlce存在并且为红色
									if (uncle!= NULL&&uncle)
									{
										parent->color = BLACK;
										uncle->color = BLACK;
										gradparent->color = RED;

										cur = gradparent;
										parent = cur->_parent;
									}
									else if (parent==gradparent->left)
									{
										if (cur == parent->left)
										{
											RotateR(grandparent);
											parent->color = BLACK;
											gradparent->color = RED;
										}
										else
										{
											RotateL(parent);
											RotateR(grandparent);
											cur->color = BLACK;
											grandparent->color = RED;
										}
										break;
									}
									else if (parent == grandparent->right)
									{
										if (cur == parent->right)
										{
											RotateL(grandparent);
											parent->color = BLACK;
											grandparent->color = RED;
										}
										else if (cur == parent->left);
										{
											RotateR(parent);
											RotateL(grandparent);
											cur->color = BLACK;
											grandparent->color = RED;
										}
										break;
									}
								}
								_root->color = BLACK;


								return true;

						  }

							  void RotateR(Node* parent)
							  {
								  Node* subL = parent->_left;
								  Node* subLR = subL->_right;

								  parent->_left = subLR;
								  if (subLR)
									  subLR->_parent = parent;

								  Node* ppNode = parent->_parent;

								  subL->_right = parent;
								  parent->_parent = subL;

								  if (parent == _root)
								  {
									  _root = subL;
									  subL->_parent = nullptr;
								  }
								  else
								  {
									  if (ppNode->_left == parent)
										  ppNode->_left = subL;
									  else
										  ppNode->_right = subL;

									  subL->_parent = ppNode;
								  }
							  }

							  void RotateL(Node* parent)
							  {
								  Node* subR = parent->_right;
								  Node* subRL = subR->_left;

								  parent->_right = subRL;
								  if (subRL)
									  subRL->_parent = parent;

								  Node* ppNode = parent->_parent;

								  subR->_left = parent;
								  parent->_parent = subR;

								  if (parent == _root)
								  {
									  _root = subR;
									  subR->_parent = nullptr;
								  }
								  else
								  {
									  if (ppNode->_left == parent)
									  {
										  ppNode->_left = subR;
									  }
									  else
									  {
										  ppNode->_right = subR;
									  }

									  subR->_parent = ppNode;
								  }
							  }

						 
							  void InOder(Node* root=_root)
							  {
								  Node* tmp = root;
								  if (tmp == NULL)
									  return;
								  InOder(tmp->_left);
								  cout << tmp->_kv.first ;
								  InOder(tmp->_right);
							  }

							  void test()
							  {
								  InOder(_root);
							  }
							  
	};
